package com.gaogzhen.algorithm.sort;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;


/**
 * 插入排序
 * 思想：希尔排序的思想是使任意间隔h的元素都是有序的。这样的数组被称为h有序数组。
 * 算法：
 * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 按增量序列个数k，对序列进行k 趟排序；
 * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 */
public class MergeImprove {

    private static Comparable[] aux;


    /**
     * 排序方法
     * @param a     实现了Comparable接口的待排序数组
     */
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);

    }

    /**
     * 对子数组排序
     * @param a     数组
     * @param lo    子数组索引起始
     * @param hi    子数组索引终止
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        // 把数组a[lo...hi]排序
        if (hi <= lo) return;
        // 如果子数组长度小于15使用插入排序
        if (hi - lo < 15)  {
            sortImprove(a);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        // 左半边数组排序
        sort(a, lo, mid);
        // 右半边数组排序
        sort(a, mid + 1, hi);
        // 归本结果
        // 左右子数组排序后，如何左数组最小（右）项小于等于右数组最小（左）项，则数组已排序完毕
        if (less(a[mid], a[mid + 1])) return;
        merge(a, lo, mid, hi);
    }

    // 内循环中将较大的元素右移而不总是交换2个元素，这样访问数组的次数就能减半
    public static void sortImprove(Comparable[] a) {

        for (int i = 1; i < a.length; i++) {
            // 保存当前元素的值
            Comparable k = a[i];
            for (int j = i; j > 0; j--) {
                // 当前元素逆序和有序元素依次比较
                if (less(k, a[j - 1])) {
                    // 当前元素小于等于前面元素，把较大的元素右移
                    a[j] = a[j-1];
                    // 如果比较到有序元素最左端，当前元素还是最小的，则吧当前元素放置索引为0的位置，结束内循环
                    if (j == 1) {
                        a[0] = k;
                        break;
                    }
                } else {
                    // 当前元素大于要比较的元素，吧当前元素插入当前位置(之前较大元素已经右移)
                    if (j != i) {
                        a[j] = k;
                    }
                    break;
                }
            }

        }
    }

    /**
     * 归并以排序的两个子数组
     * @param a         数组
     * @param lo        子数组1起始索引
     * @param mid       子数组1终止索引，mid+1子数组2起始索引
     * @param hi        子数组2终止索引
     */
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 将a[lo...mid]和a[mid+1...hi]归并
        int i = lo, j = mid + 1;
//        for (int k = lo; k <= hi; k++) {
//            aux[k] = a[k];
//        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) aux[k] = a[j++];
            else if (j > hi) aux[k] = a[i++];
            else if (less(a[j], a[i])) aux[k] = a[j++];
            else aux[k] = a[i++];
        }
        Comparable[] t = a;
        a = aux;
        aux = t;
    }

    /**
     * 比较大小
     * @param a     目标a
     * @param b     目标b
     * @return      返回布尔值
     */
    private static  boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 交换数组元素
     * @param a     数组
     * @param i     索引
     * @param j     索引
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a     数组
     */
    private static void show(Comparable[] a) {
        // 单行打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    /**
     * 测试数组是否已经有序
     * @param a     带测试数组
     * @return      测试结果: true-数组有序；false-数组无序
     */
    public static boolean isSorted(Comparable[] a) {
        // 测试数组是否已经有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) return false;
        }
        return  true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将他们排序并输出
        String[] a = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
